The present invention relates to computer graphics generation and display, and more particularly, to computer graphics generation display with reduced need for accessing a z-buffer during the generation and display of graphical images.
A computer graphics display system allows displays of graphical images on pixel-oriented output devices. FIG. 1 is a simplified, semi-schematic block diagram of one such exemplary system. As illustrated in FIG. 1, the system comprises a processor 10, a frame buffer 12, a display monitor 14, and a display controller 16. The display monitor 14 includes a screen which displays a plurality of pixels, a pixel being the smallest addressable element in an electronic display. The individual pixels on the screen are addressed using x and y coordinates, in the same manner as points on a graph are addressed.
The frame buffer 12 resides in main memory 18 and stores a pixel number map corresponding to a graphical image. The pixel number map can be represented by a grid-like array of pixels where each pixel is assigned a color and a shade value. Typically, those values are represented as R, G, B, and A values corresponding to the red color, green color, blue color, and the intensity values of the pixel making up the graphical image. The number of bits defining the R, G, B, and A values depend on the number of colors and shades to be represented.
The processor computes and updates the pixel values in the frame buffer 12 when a new graphical image 13 is to be displayed. During the display process, the display controller 16 acts as an interface between the frame buffer 12 and the display monitor 14 by taking the pixel values in the frame buffer and converting them to a video signal for display by the monitor.
In processing a three-dimensional graphical object, the depth attribute of the object must be considered prior to the updating of any pixel values in the frame buffer. If the new object being processed is located behind and is partially obscured by the displayed object, only a visible portion of the new object should be displayed. On the other hand, if the new object is completely obscured by the displayed object, no updates to the frame buffer is necessary and the new object is not displayed.
Three-dimensional objects are often represented by a set of vertices defining polygon surfaces. Each vertex is defined by x, y, and z dimensions corresponding to the X, Y, and Z axes. The X and Y axes define a view plane and the Z axis represents a distance from the view plane. A z coordinate value, therefore, indicates the depth of an object at a pixel location defined by specific x and y coordinates.
A z-buffer 20 storing the z-value of each pixel, and hence, the depth value of each pixel, permits performance of depth analysis of a three-dimensional object. This process is often referred to as a xe2x80x9chidden surface removal process.xe2x80x9d When a new object moves into a displayed portion of the view plane, a determination must be made as to whether the new object is visible and should be displayed, or whether the new object is hidden by objects already in the displayed portion of the view plane. The determination of whether the new object should be displayed is generally done on a pixel-by-pixel basis. Thus, for each pixel, defined by x-y coordinates, the depth, or z-value, of the new object is compared to the depth, or z-value, of the currently displayed object. If the comparison indicates that the new pixel to be drawn is in front of the old pixel in the z-buffer (i.e. the new z-value is less than the old z-value), the old z-value is replaced with the new z-value, and the R, G, B, and A values for the new pixel are written to the frame buffer for being displayed in the place of the old pixel. On the other hand, if the new pixel is located behind the old pixel, it will be hidden from view and need not be displayed. In this situation, the old z-value is kept in the z-buffer and the new z-value is discarded. The old pixel remains displayed and is not replaced by the new pixel.
There are several disadvantages to the above process. First, initializing each pixel in the z-buffer to a constant value (generally the value of the background) is expensive in terms of time and memory bandwidth. Furthermore, the pixel-by-pixel analysis during the display of an object requires a z-buffer read for each pixel to compare the z-value of the old pixel with respect to the new pixel. Because z-buffers are large and cannot be stored on-chip, thereby requiring external memory access, such z-comparisons significantly slow down the display process. In addition, significant computational cycles are expended in performing pixel-by-pixel comparisons. Accordingly, there is a need for a system and method for computer graphics generation and display that will perform hidden surface removal with less computation cycles and memory bandwidth waste.
The present invention specifically addresses and alleviates the above-mentioned deficiencies associated with the prior art. More particularly, the present invention comprises a computer graphics display system that eliminates the initialization of the z-buffer to a constant value. In addition, the system performs z-comparisons on groups of pixels thereby reducing the number of z-buffer accesses for performing pixel-by-pixel comparisons.
In accordance with one aspect of the invention, a screen is partitioned into a plurality of display blocks having one or more layers of pixels. A z-range buffer is generated for storing minimum and maximum depth values of the layers of a display block. The z-range buffer further stores a bitmask value where each bit in the bitmask associates a pixel in the block to a particular layer in the block. The system compares a depth value of a polygon with a depth value of a particular layer, and identifies visible pixels in the block making up the polygon based on the comparison.
In another aspect of the invention, the polygon over the block is a triangle.
In yet another aspect of the invention, each block has two layers corresponding to a front layer and a back layer, each layer having depth values ranging from a minimum depth value to a maximum depth value.